package arithmetic.leetcode;



import java.util.*;

public class DtghTest {

    public static void main(String[] args) {

    }

    /**
     * Leetcode - 20 有效的括号
     * 栈结构--先进后出
     *
     */
    private static boolean extracted(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if(c == '('){
                stack.push(')');
            }else if(c == '['){
                stack.push(']');
            }else if (c == '{'){
                stack.push('}');
            }else if(stack.isEmpty() || stack.pop() != c){
               return false;
            }
        }
        return stack.isEmpty();
    }


    /**
     * Leetcode-136 只出现一次的数字
     * 给定一个非空整数数组，除了某个元素只出现一次以外,其余每个元素均出现两次
     *  使用 ^ 异或 = 任何一个数和自己异或的结果一定是0;
     *  & 与运算:都是1则为1,有一个为0则为0
     *  | 或运算:都是0则为0,有一个为1则为1
     */
    public static int singleNumber(int[] nums){
        int result = 0;
        for (int num : nums){
            result = result ^ num;
        }
        return result;
    }

    /**
     * Leetcode - 415
     * 给定两个字符串形式的非负整数num1和num2，计算他们的和并同样已字符串返回
     * 字符串相加
     * 例如:num1 = "456",num2 = "77";
     * 输出:533
     * 利用字符的ASCII码  任何一个整数的字符的ASCII与字段'0'相减就是对应的整数
     */
    public static String addStrings(String num1,String num2){
        StringBuffer sb = new StringBuffer();
        //记录进位的变量
        int carry = 0;
        for (int i = num1.length()-1,j = num2.length()-1;i >= 0 || j >= 0 || carry == 1;i--,j--){
            int x = i < 0 ? 0 : num1.charAt(i) - '0';
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            sb.append((x+y+carry) % 10);
            carry = (x+y+carry)/10;
        }
        return sb.reverse().toString();
    }

    /**
     * 字符串匹配
     * 字符串匹配值BF算法-暴力穷举算法:
     *      以模式串的第一个字符开始比较,如果不相同向右移动
     *
     * 字符串匹配之BM算法：
     *      坏字符：坏字符的位置-模式串中的上一次出现的位置
     *      好字符：好字符的位置-模式串中的上一次出现的位置
     *
     *  字符串匹配之KMP算法：
     *      字符串:bread
     *      前缀：b,br,bre,brea
     *      后缀：read,ead,ad,d
     *      记录一个部分匹配值表
     */

    /**
     * 游戏背包
     * 小偷去某商店盗窃，背有一个背包，容量是5kg,现在有以下物品，请问小偷如何拿才能得到最大的价值
     * 物品1 1kg 6元
     * 物品2 2kg 10元
     * 物品3 4kg 12元
     * 里面的表格就表示当前重量下能装下的最大值。表格的列就表示要装的物品
     *       1kg 2kg 3kg 4kg 5kg
     * 物品1  6   6   6   6   6
     * 物品2  6   10  16  16  16
     * 物品3  6   10  16  16  18
     *
     * 状态转移方程:能装的时候,每次和上面的比较,大我就装,否则就不装
     * 去最大值
     * Max(
     *  money[i] + dp[i-1][w-weight[i]],
     *  dp[i-1][w]
     * );
     *
     */
    public static void bB(){
        int[] value = {6,10,12};
        int[] weight = {1,2,3};
        int w = 5;//背包的重量
        int n = 3;//表示物品
        int[][] dp = new int[n+1][w+1];
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= w; j++){
                if(weight[i-1] <= j){ //表示这个物品可以装进去
                    dp[i][j] = Math.max(
                      value[i-1] + dp[i-1][j-weight[i-1]],
                        dp[i-1][j]
                    );
                }{
                   dp[i][j] = dp[i-1][j];//不能装
                }
            }
        }
        System.out.println(dp[n][w]);
    }

    /**
     * 购物车问题:清空购物车5000元
     */
    public static void gwc(){
        int[] value = {1,2,5,6,4,1,9};
        int w =8;//w代码价格最大值
        int n =7;//n代表7个物品
        int[][] dp = new int[n+1][w+1];
        for (int i =1; i < n; i++){
            for (int j = 1; j<= w; j++){
                if(value[i-1] <= j){//表示物品1的价格可以放进去
                    dp[i][j] = Math.max(
                            value[i-1] + dp[i-1][j-value[i-1]],
                            dp[i-1][j]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

    }

    /**
     * 子数组的最大平均数
     *  给定一个整数数组,找出平均数最大且长度为K的下标连续的子数组,并输出该最大平均数
     *  滑动窗口解决 -- 双指针的特例
     */
    public static double findMaxAverage(int[] nums, int k){
        int sum = 0;//记录总和
        int n = nums.length;
        //先统计第一个窗口的和
        for (int i = 0; i < k; i++){
            sum += nums[i];
        }
        int max = sum;
        for (int i = k; i < n; i++){
            //减掉滑动窗口的第一个值,加入新家的值
            sum = sum - nums[i - k] + nums[i];
            max = Math.max(max, sum);
        }
        return 1.0 * max / k;
    }

    /**
     * LeetCode-215 数组中的第K个最大元素
     * 给定整数数组nums和整数K,请返回数组中第K个最大的元素
     * 【3,2,1,5,6,4】 和 K=2
     * 输出:5
     * 先排序-通过快排序/堆排序,排好序然后找出
     */
    public static int findKthLargest(int[] nums, int k){
        int n = nums.length;
        Arrays.sort(nums);//先排序-快速排序
        return nums[n - k];
    }

    /**
     * LeetCode-347 前K个高频元素
     * 给定一个整数数组nums和一个整数K,请你返回其中出现频率前K高的元素
     * nums = [1,1,1,2,2,3] , k=2;
     * 输出:[1,2]
     * 堆排序
     */
    public static int[] topKFrequent(int[] nums, int k){
        Map<Integer, Integer> map = new HashMap<>();
        //统计每个元素出现的频率
        for (int n : nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }
        //最小堆
        //每个放进优先队列的数组int[]只有两个元素:第一个元素代表数组的值,第二个元素代表该值出现的次数。
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(k,(a,b) -> (a[1]-b[1]));
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            int count = entry.getValue();
            if(minHeap.size() == k){
                if(minHeap.peek()[1] < count){
                    minHeap.poll();
                    minHeap.offer(new int[]{entry.getKey(),count});
                }
            }else {
                minHeap.offer(new int[]{entry.getKey(),count});
            }
        }
        //把元素以数组的形式返回
        int[] result = new int[k];
        for (int i = 0; i < k; i++){
            result[i] = minHeap.poll()[0];
        }
        return result;
    }

    /**
     * LeetCode-15 三数之和
     * 给你一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a+b+c=0？请你找出所有和为0且不重复的三元组。
     * num[-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     *
     * 注意：不可以包含重复的三元组
     *
     * 1、暴力穷举 三层循环 时间复杂度O(n^3)
     * 2、暴力穷举 双层循环 + hashmap（map的key为nums[i],value是i）--时间复杂度O(n^2)
     * for(int i =0; i< nums.length; i++){
     *     map.put(nums[i],i);
     * }
     * 3、排序+双指针
     *
     */
    public static List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> results = new LinkedList<>();
        if (nums.length<3){//长度小于3就不存在三数之和了
            return results;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for (int i =0; i < n; i++){
            if(nums[i] > 0){
                //如果第一个数就大于0,就没有必要查找下去了
                break;
            }
            int head = i + 1, tail = n - 1;
            while (head < tail){
                int sum = nums[i] + nums[head] + nums[tail];
                if(sum < 0){
                    head++;
                }else if(sum > 0){
                    tail--;
                }else {
                    //三数之和等于0
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[i]);
                    list.add(nums[head]);
                    list.add(nums[tail]);
                    results.add(list);
                    //进行去重
                    while (head + 1 <= tail && nums[head] == nums[head + 1]){
                        head++;
                    }
                    while (head + 1 <= tail && nums[tail] == nums[tail-1]){
                        tail--;
                    }
                    head++;
                    tail--;
                }
            }
            //去重
            while (i+1 < n && nums[n] == nums[n+1]){
                i++;
            }
        }
        return results;
    }

    /**
     * LeetCode-4
     * 寻找两个正序数组的中位数
     * 给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2.请你找出并返回这两个正序数组的中位数
     * 中位数:分奇数/偶数
     * 例子：nums1 ={1,3},nums2 = {2};
     *      输出 2;
     * 例子：nums1 ={1,2},nums2 ={3,4};
     *      输出 2.5
     * 1、最笨的办法是合并两个有序数组,然后判断数组的长度是偶数还是奇数,然后算中位数
     *      O(m+n);
     * 二分查找：log(m+n);
     * 2、
     *
     */


}
